(1) Field of the Invention
This invention relates to joint MAC and routing schemes for wireless ad-hoc networks. More specifically, this invention relates to joint MAC, routing, and power schemes that consider problems associated with interference.
(2) Description of Related Art
Open Systems Interconnection (OSI) is a well-known standard description or “reference model” for how messages should be transmitted between any two points in a communication network and is available in numerous publications, including a book by Andrew S. Tanenbaum titled “Computer Networks,” second edition, Prentice-Hall, Inc., 1988 (hereinafter Tanenbaum). The main idea in OSI is that the process of communication between two end points in a communication network can be divided into layers, with each layer adding its own set of special, related functions. As illustrated in the prior art FIG. 1, the OSI divides communication into seven layers. The upper four layers are used whenever a message passes from or to a user and the lower three layers (up to the network layer) are used when any message passes through the host system. Messages intended for the host system pass to the upper layers, and messages destined for some other host are not passed to the upper layers but, instead, are forwarded to another host.
The first (physical) layer 1 is concerned with transmitting raw bits over a communication channel. This layer 1 defines the electrical and other physical characteristics of the network such as voltage, current, and power levels for transmission of actual raw data, data rates, maximum transmission distance, etc. Typical design issues for this layer 1 deal with power requirements to transmit information, how many microseconds a bit lasts, whether transmission may proceed simultaneously in both directions, how the initial connection is established and how the connection is torn down when both sides are finished.
The main task of the Data Link layer 2 is to take a raw transmission facility and transform it into a line that appears free of transmission errors to the network layer 3. This task is accomplished by having the sender break the input data up into data frames, transmit the frames sequentially, and process the acknowledged frames sent back by the receiver. Since the physical layer 1 merely accepts and transmits a stream of bits without any regard to meaning or structure, it is up to the data link layer 2 to create and recognize frame boundaries. As illustrated in prior art FIG. 2, the Data Link layer 2 divides into two well-known sub-layers, a Logic Link Control (LLC) sub-layer 202 and a Medium Access Control (MAC) sub-layer 200. The LLC sub-layer 202 manages communication between devices over a single line of a network. The MAC sub-layer 200 manages access to the physical network medium. The Institute of Electrical and Electronics Engineers (IEEE) MAC specification defines MAC addresses, which enable multiple devices to identify one another at the data link layer 2. The last layer discussed in detail is the network layer 3 (layer 3 in OSI) that defines the network address, which differs from the MAC address. The network layer 3 is concerned with getting packets from the source all the way to the destination. It is the lowest layer that deals with end-to-end transmission.
The prior art FIG. 3 shows an example of how data can be transmitted using OSI model. The seven OSI layers use various forms of control information (the headers) to communicate with their peer layers in other systems. This control information is comprised of specific requests and instructions, exchanged between peer OSI layers. The details of all the layers and their respective communication protocols are well-known. However, the instant invention will consider layers one to three in more details. As illustrated in both FIGS. 1 and 3, a frame is an information unit (a unit of exchange) whose source and destination are data link layer 2 entities. A frame (generally measured in units of time) is composed of the data link layer header 304 (and possibly a trailer) and upper-layer data. The header 304 and trailer (not shown) contain control information intended for the data link layer 2 entity in the destination system. Data from upper-layer entities (Packets from Network Layer 3) encapsulate in the data link layer header 304 and trailer (not shown). A packet is an information unit whose source and destination are network layer 3 entities. A packet is composed of the network layer header 302 (and possibly a trailer—not shown) and upper-layer data. The header 302 and trailer contain control information intended for the network layer 3 entity in the destination system. Data from upper-layer entities encapsulate in the network layer 3 header 302 and trailer. Exchange unit for layer 1 is a bit, layer 2 exchange unit is a frame, layer 3 exchange unit is a packet, layer 4 exchange unit is a Transport Protocol Data Unit (TPDU), layer 5 exchange unit is a Session Protocol Data Unit (SPDU), layer 6 exchange unit is a Presentation Protocol Data Unit (PPDU), and layer 7 exchange unit is an Application Protocol Data Unit (APDU).
The problem with the OSI model is the study, research, and implementation of layers in isolation. On one hand, major work has been devoted to maximizing spatial reuse while minimizing interference (collisions) that may arise at various receivers. This, in turn, involves preventing primary and secondary interference in addition to handling the hidden and exposed terminal problems. MAC schemes (layer 2) for ad-hoc networks can be broadly classified into contention-based and reservation-based schemes. Under the former classification, carrier sense multiple access (CSMA), carrier sense multiple access with collision avoidance (CSMA/CA), and other collision avoidance mechanisms have been extensively studied and evaluated. In addition, others, such as, busy tone multiple access schemes introduced in various publications have attempted to solve the hidden and exposed terminal problems. Under the reservation-based class, scheduling non-conflicting transmissions in a distributed fashion has been the focal point of various other studies. However, the aforementioned schemes are confined to layer 2 in the International Standards Organization (ISO) OSI protocol stack and do not address the interaction and trade-off with (or across) higher and lower layers. For instance, none of the above schemes address the impact of power and data rate control at the physical layer 1 on the MAC decision taken at the layer 2. Moreover, the interaction between the MAC and routing layers decisions is not investigated.
In general, the use of multi-hop paths to transport data between source and destination nodes has been shown to enhance the network capacity. Research efforts in the routing arena (multi-hop routing in wireless networks) have been focused primarily in the following two directions: i) efficient route discovery/maintenance under mobility conditions and topology changes and ii) modifying the routing/link metric to match a wide variety of objectives (i.e., performance requirements). Most of the protocols developed along the former research direction (i) adopt the shortest path (SP) routing criteria widely employed in wireline networks. Along the second research direction (ii), considerable attention has been given to modifying the routing metric to meet different requirements. For instance, the proposed class of energy efficient routing metrics is targeted to evenly distribute the network load among nodes according to their residual battery charges in order to increase the network lifetime. In other studies, the routing criteria incorporate the received signal strength so those routes with stable links are favored over routes with vulnerable links. Finally, other studies introduced a least-resistance routing metric for frequency hopping ad-hoc networks. However, studies relying on signal strength or least-resistance routing metrics did not consider the interference-induced coupling between the MAC layer and routing layer decisions.
Recently, the interactions between various layers in the OSI stack have started to receive some attention, including, for example, the role of power and rate control (physical layer) in improving the CSMA/CA (data link layer) throughput performance. Introducing power control to CSMA/CA was targeted at improving the network capacity by achieving denser spatial reuse and the rate control was used to exploit the wireless channel conditions such that the rate could increase when the channel condition was good and decreased when poor.
There have also been few attempts to couple MAC layer protocol design to routing layer, which include interactions between the two layers under different mobility models. The results indicated were two-fold: i) the performance varies depending on the traffic type and mobility patterns and ii) there is no “absolute winner” for the routing/MAC combination. More recently, some efforts have been devoted to coupling routing, scheduling, and physical layer design in wireless ad-hoc networks. The work done by Cruz et al. in a publication titled “Optimal Routing, Link Scheduling and Power Control in Multi-hop Wireless Networks,” PROC. IEEE INFOCOM, April 2003 (hereinafter the Cruz et al. article), the entire disclosure of which is incorporated herein by reference, addresses some of the problems of joint routing, scheduling, and power control to support high data rates in wireless multi-hop networks. Although the work done formulates some joint scheduling and power control as an optimization problem, the optimum is determined for given topology and data rate requirements over each link. That is, using the Gaussian approximation for interference, the Cruz et al. article characterizes the optimal scheduling and power control policy that minimizes the total average transmission power subject to constraints on the link data rates and peak power per node. This facilitates the use of shortest-path (SP) routing with a link metric derived from the multiple access problem formulation. Other studies address the same problem in the context of symmetric one-dimensional multi-hop networks with the objective of finding the policy that achieves max-min fair rate allocation.
Joint routing and scheduling metrics for wireless ad-hoc networks that attempt to balance the trade-off between energy consumption and delay are also introduced in some studies. Others use a separate control channel to emphasize the interplay between MAC and routing through power control. Finally, the set of all data rates that stabilizes a network of time-varying wireless links, characterized by rate-power functions that incorporate interference, has also been studied by Neely et al. in a publication titled “Dynamic Power Allocation and Routing for Time Varying Wireless Networks,” Proc. IEEE INFOCOM, April 2003, the entire disclosure of which is incorporated herein by reference. Moreover, a joint routing and power allocation strategy that offers delay guarantees has also been developed.
However, a cross-layer framework for multiple access and routing design in wireless ad-hoc networks that addresses the role of multi-user interference is not addressed by the prior art. Therefore, there is a need to modify a link metric in view of multi-user interference. In state of the art ad-hoc networks, the routing decision is completely independent from the MAC decision. Thus, the routing decision could potentially lead to degrading the performance of the multiple access protocol, which eventually leads to degrading the end-to-end network throughput. Most routing algorithms introduced for wireless ad-hoc networks rely on the classical shortest-path (SP) or minimum-hop (MH) routing criteria. Although these routing criteria could be attractive from the point of view of network throughput and end-to-end delays, they have a fundamental limitation in wireless networks. This limitation stems from the fact that each source-destination pair compute SP or MH routes independently. They do not take into consideration the relation and interaction among the chosen paths or the amount of multi-user interference a certain path may introduce to the receivers on other paths. That is, this routing criterion ignores the possibility of network congestion induced by multi-user interference coupling between spatially close links. Hence, the prior art overlooks the effect of routing decisions on the performance of multiple access algorithms. The prior art has focused primarily on improving the end-to-end throughput via reducing path lengths that primarily use SP routing algorithms.
In light of the current state of the art and the drawbacks to current systems mentioned above, a general need exists for a system and a method that would address the interaction and trade-off with (or across) higher and lower layers of the wireless OSI network communication. More specifically, a need exists for a system and a method that would address the role of multi-user interference within the environment of the cross-layer framework for multiple access and routing design in wireless ad-hoc networks.